package leecode;

import java.util.Arrays;

/**
 * @author csp 2021-04-25
 */
public class QuickSort {

    public int[] sort(int[] nums) {
        int l = 0, r = nums.length - 1;
        fastsort(l, r, nums);
        return nums;
    }

    public static void main(String[] args) {
        QuickSort sort = new QuickSort();
        final int[] sort1 = sort.sort(new int[]{1, 9, 5});
        System.out.println(Arrays.toString(sort1));
    }
    public void fastsort(int l, int r, int[] s) {
        if (l < r)
        {
            //Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
            int i = l, j = r, x = s[l];
            while (i < j)
            {
                while(i < j && s[j] >= x) // 从右向左找第一个小于x的数
                    j--;
                if(i < j)
                    s[i++] = s[j];

                while(i < j && s[i] < x) // 从左向右找第一个大于等于x的数
                    i++;
                if(i < j)
                    s[j--] = s[i];
            }
            s[i] = x;
            fastsort(l, i - 1, s); // 递归调用
            fastsort(i + 1, r, s);
        }
    }

}
